package org.wuxinshui.boosters.nowcoder.classicQuestion;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 描述
 * <p>
 * 求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
 * <p>
 * 示例1
 * <p>
 * 输入：
 * {1,2,3,4,5}
 * <p>
 * 返回值：
 * 2
 * <p>
 * * public class TreeNode {
 * *   int val = 0;
 * *   TreeNode left = null;
 * *   TreeNode right = null;
 * * }
 *
 */
public class CC1TreeNode {

    public static void main(String[] args) {
        CC1TreeNode solution = new CC1TreeNode();

        // 测试用例1: [3,9,20,null,null,15,7]
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);
        System.out.println("最小深度: " + solution.minDepth(root1)); // 输出: 2

        // 测试用例2: [2,null,3,null,4,null,5,null,6]
        TreeNode root2 = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.right.right = new TreeNode(4);
        root2.right.right.right = new TreeNode(5);
        root2.right.right.right.right = new TreeNode(6);
        System.out.println("最小深度: " + solution.minDepth(root2)); // 输出: 5

        // 测试用例3: 空树
        System.out.println("最小深度: " + solution.minDepth(null)); // 输出: 0
    }

    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 如果左子树为空，只计算右子树
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }

        // 如果右子树为空，只计算左子树
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }

        // 左右子树都不为空，取较小值
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }


    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }


    }


    /**
     * BFS（推荐）
     */
    public int minDepth_BFS(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                // 找到第一个叶子节点，立即返回当前深度
                if (node.left == null && node.right == null) {
                    return depth;
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            depth++;
        }

        return depth;
    }

    /**
     *DFS（非递归
     */
    public int minDepth_DFS(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root, 1));
        int minDepth = Integer.MAX_VALUE;

        while (!stack.isEmpty()) {
            Pair current = stack.pop();
            TreeNode node = current.node;
            int currentDepth = current.depth;

            // 如果是叶子节点，更新最小深度
            if (node.left == null && node.right == null) {
                minDepth = Math.min(minDepth, currentDepth);
            }

            if (node.left != null) {
                stack.push(new Pair(node.left, currentDepth + 1));
            }
            if (node.right != null) {
                stack.push(new Pair(node.right, currentDepth + 1));
            }
        }

        return minDepth;
    }

    class Pair {
        TreeNode node;
        int depth;

        Pair(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
}
